﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Searches
{
    /// <summary>
    /// http://algolist.manual.ru/olimp/rec_prb.php
    /// </summary>
    public static class Olimpic
    {
        /// <summary>
        /// Вычислить значение суммы S = 1/1! + 1/2! + ... + 1/k!
        /// </summary>
        /// <param name="k"></param>
        /// <returns></returns>
        public static double Task1(int k)
        {
            double result = 0;

            for (int i = 1; i <= k; i++)
            {
                result += i / Factorial(i);
            }

            return result;
        }

        /// <summary>
        /// Написать программу определения количества шестизначных 'счастливых' билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр
        /// </summary>
        /// <returns></returns>
        public static int Task2()
        {
            int counter = 0;

            for (int i = 0; i < 1000000; i++)
            {
                int firstSign = i / 100000;
                int secondSign = (i - firstSign * 100000) / 10000;
                int thirdSign = (i - firstSign * 100000 - secondSign * 10000) / 1000;
                int fourthSign = (i - firstSign * 100000 - secondSign * 10000 - thirdSign * 1000) / 100;
                int fifthSign = (i - firstSign * 100000 - secondSign * 10000 - thirdSign * 1000 - fourthSign * 100) / 10;
                int sixthSign = (i - firstSign * 100000 - secondSign * 10000 - thirdSign * 1000 - fourthSign * 100 - fifthSign * 10);

                if (firstSign + secondSign + thirdSign == fourthSign + fifthSign + sixthSign)
                    counter += 1;
            }

            return counter;
        }

        /// <summary>
        /// Написать программу определения количества 2*N -значных билетов, у которых сумма первых N десятичных цифр равна сумме N последних десятичных цифр; при этом N -произвольное натуральное число.
        /// </summary>
        /// <returns></returns>
        public static int Task3(int n)
        {
            int counter = 0;
            int[] signs = new int[2 * n];

            for (int i = 0; i < Math.Pow(10, 2 * n); i++)
            {
                for (int j = 0; j < signs.Length; j++)
                {
                    int result = i;

                    for (int k = 0; k < j; k++)
                    {
                        result -= signs[k] * (int)Math.Pow(10, 2 * n - k - 1);
                    }

                    signs[j] = result / (int)Math.Pow(10, 2 * n - j - 1);
                }

                if (signs.Take(n).Sum() == signs.Skip(n).Sum())
                    counter += 1;
            }

            return counter;
        }

        /// <summary>
        /// Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.
        /// </summary>
        /// <param name="n"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int Task4(int n, int k)
        {
            return Enumerable.Range(1, k).Sum(x => Task4Impl(n, k, x));
        }

        private static int Task4Impl(int n, int k, int currentPosition)
        {
            if (currentPosition == n)
                return 1;
            if (currentPosition > n)
                return 0;

            return Enumerable.Range(1, k).Sum(x => Task4Impl(n, k, currentPosition + x));
        }



        /// <summary>
        /// Задан массив М [1:N] натуральных чисел, упорядоченный по неубыванию, т.е.: M[1]<=M[2]<=...<=M[N].
        /// Найти первое натуральное число, не представимое суммой никаких элементов этого массива, при этом сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз.
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int Task6(params int[] array)
        {
            List<bool[]> indeces = new List<bool[]>();
            for (int i = 1; i <= array.Length * array.Length; i++)
            {
                int current = i;
                bool[] index = new bool[array.Length];
                for (int j = 0; j < array.Length; j++)
                {
                    index[j] = current % 2 == 1;
                    current /= 2;
                }

                indeces.Add(index);
            }

            List<int> list = indeces.Select(x => array.Select((item, index) => new { item, index }).Where(item => x[item.index]).Sum(item => item.item)).OrderBy(x => x).ToList();
            for (int i = 1; i < list.Count; i++)
            {
                if (list[i] - list[i - 1] > 1)
                {
                    return list[i - 1] + 1;
                }
            }

            return list[list.Count - 1] + 1;
        }

        /// <summary>
        /// По матрице A(N,N) построить матрицу B(N,N). 
        /// Элемент B(I,J) равен максимальному из элементов матрицы А принадлежащем части, ограниченной справа диагоналями, проходящими через A(I,J).
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[,] Task9(this int[,] array)
        {
            int[,] result = new int[array.GetLength(0), array.GetLength(1)];
            for (int i = 0; i < array.GetLength(0); i++)
            {
                for (int j = 0; j < array.GetLength(1); j++)
                {
                    int currentSum = 0;

                    for (int x = i, y = j; x >= 0 && y >= 0; x--,y-- )
                    {
                        for (int k = 0; k <= y; k++)
                        {
                            currentSum += array[x, k];
                        }
                    }

                    for (int x = i + 1, y = j - 1; x < array.GetLength(0) && y >= 0; x++, y--)
                    {
                        for (int k = 0; k <= y; k++)
                        {
                            currentSum += array[x, k];
                        }
                    }

                    result[i, j] = currentSum;
                }
            }

            return result;
        }

        public static int[,] FillMatrixRightToDiagonals(int size)
        {
            int[,] result = new int[size, size];
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    if (i >= j && i < size / 2 || i <= size - j - 1 && i >= size/2)
                    {
                        result[i, j] = 1;
                    }
                }
            }

            return result;
        }

        public static int[,] FillMatrixDiagonals(int width, int height, int x, int y)
        {
            int[,] result = new int[width, height];
            int x1 = x >= y ? x - y : 0;
            int y1 = x >= y ? 0 : y - x;

            for (; x1 < width && y1 < height; x1++, y1++)
            {
                result[x1, y1] = 1;
            }

            x1 = (width - x - 1) >= y + 1 ? width - x - y : width - 1;
            y1 = (width - x - 1) >= y ? 0 : y - (width - x - 1);

            for (; x1 > 0 && y1 < height; x1--, y1++)
            {
                result[x1, y1] = 1;
            }

            return result;
        }

        private static double Factorial(int i)
        {
            if (i <= 1)
            {
                return 1;
            }

            return i * Factorial(i - 1);
        }
    }
}